import java.util.Arrays;

public class Solution329 {
    int[] dx={1,0,-1,0};
    int[] dy={0,1,0,-1};

    public int longestIncreasingPath(int[][] matrix) {
        int[][] f=new int[matrix.length][matrix[0].length];
        for (int[] ints : f) {
            Arrays.fill(ints,-1);
        }
        int ans=0;
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                ans=Math.max(ans,dfs(i,j,f,matrix));
            }
        }
        return ans;
    }

    private int dfs(int m, int n, int[][] f, int[][] matrix) {
        if (f[m][n]!=-1){
            return f[m][n];
        }
        f[m][n]=1;
        for (int i=0;i<4;i++){
            int x=m+dx[i];
            int y=n+dy[i];
            if (valid(x,y,matrix.length,matrix[0].length) && matrix[x][y]<matrix[m][n]){
                f[m][n]=Math.max(dfs(x,y,f,matrix)+1,f[m][n]);
            }
        }
        return f[m][n];
    }

    private boolean valid(int x, int y, int m, int n) {
        return x>=0 && x<m && y>=0 && y<n;
    }

    public static void main(String[] args) {
        System.out.println(new Solution329().longestIncreasingPath(new int[][]{{9,9,4},{6,6,8},{2,1,1}}));
    }
}
